<html>
<head>
  <title>Module 1: Neural Networks</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="816"/>
<h1>Module 1: Neural Networks</h1>

<div>
<span><div><div><div><div><br/></div><h2 style="text-align: center;"><span style="font-size: 24pt; color: rgb(28, 51, 135);">Image Classification</span></h2><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Motivation</span></div><div>        assigning an input image one label from a fixed set of categories.has a large variety of practical applications.  many<span style="line-height: 1.45;"> </span><span style="line-height: 1.45;">other seemingly distinct Computer Vision tasks (such as object detection, segmentation) can be reduced to image classification.</span></div><div>                   </div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Example</span></div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image.png" type="image/png" data-filename="Image.png"/></div><div>        The task in Image Classification is to predict a single label (or a distribution over labels as shown here to indicate our confidence) for a given image. Images are 3-dimensional arrays of integers from 0 to 255, of size Width x Height x 3. The 3 represents the three color channels Red, Green, Blue.</div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Challenges</span></div><ul><li><span style="font-weight: bold;">Viewpoint variation</span>. A single instance of an object can be oriented in many ways with respect to the camera.</li><li><span style="font-weight: bold;">Scale variation</span>. Visual classes often exhibit variation in their size (size in the real world, not only in terms of their extent in the image).</li><li><span style="font-weight: bold;">Deformation</span>. Many objects of interest are not rigid bodies and can be deformed in extreme ways.</li><li><span style="font-weight: bold;">Occlusion</span>. The objects of interest can be occluded. Sometimes only a small portion of an object (as little as few pixels) could be visible.</li><li><span style="font-weight: bold;">Illumination conditions</span>. The effects of illumination are drastic on the pixel level.</li><li><span style="font-weight: bold;">Background clutter</span>. The objects of interest may <span style="font-style: italic;">blend</span> into their environment, making them hard to identify.</li><li><span style="font-weight: bold;">Intra-class variation</span>. The classes of interest can often be relatively broad, such as <span style="font-style: italic;">chair</span>. There are many different types of these objects, each with their own appearance.</li></ul><div><br/></div><div><img src="Module 1 Neural Networks_files/Image.jpg" type="image/jpeg" data-filename="Image.jpg"/></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Data-driven approach</span></div><div><font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">How might we go about writing an algorithm that can classify images into distinct categories?</span></font></div><div>        instead of trying to specify what every one of the categories of interest look like directly in code,we’re going to provide the computer with many examples of each class and then develop learning algorithms that look at these examples and <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">learn about the visual appearance of each class</span></font>.</div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">The image classification pipeline</span></div><ul><li><span style="font-weight: bold;">Input:</span> Our input consists of a set of <span style="font-style: italic;">N</span> images, each labeled with one of <span style="font-style: italic;">K</span> different classes. We refer to this data as the <span style="font-style: italic;">training set</span>.</li><li><span style="font-weight: bold;">Learning:</span> Our task is to use the training set to learn what every one of the classes looks like. We refer to this step as <span style="font-style: italic;">training a classifier</span>, or <span style="font-style: italic;">learning a model</span>.</li><li><span style="font-weight: bold;">Evaluation:</span> In the end, we evaluate the quality of the classifier by asking it to predict labels for a new set of images that it has never seen before. We will then compare the true labels of these images to the ones predicted by the classifier. Intuitively, we’re hoping that a lot of the predictions match up with the true answers (which we call the <span style="font-style: italic;">ground truth</span>).</li></ul><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><h3 style="text-align: left;"><span style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: normal;">Nearest Neighbor Classifier</span></h3><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Example image classification dataset: CIFAR-10</span></div><div>        One popular toy image classification dataset is the <a href="http://www.cs.toronto.edu/~kriz/cifar.html">CIFAR-10 dataset</a>. This dataset consists of 60,000 tiny images that are 32 pixels high and wide. Each image is labeled with one of 10 classes (for example <span style="font-style: italic;">“airplane, automobile, bird, etc”</span>). These 60,000 images are partitioned into a training set of 50,000 images and a test set of 10,000 images.</div><div>        given two images and representing them as vectors <span style="position: absolute; width: 0.869em; height: 0px; font-size: 122%; clip: rect(3.159em 1000.5em 4.15em -1000em); top: -3.996em; font-family: MathJax_Math; font-style: italic;">I</span><span style="position: absolute; width: 0.869em; height: 0px; font-size: 70.7%; clip: rect(1.469em 1002.2em 2.653em -1000em); top: -3.846em; font-family: MathJax_Main;">1</span><span style="position: absolute; width: 2.203em; height: 0px; font-size: 122%; clip: rect(1.469em 1002.2em 2.653em -1000em); top: -2.305em; font-family: MathJax_Main;">,</span><span style="position: absolute; width: 0.869em; height: 0px; font-size: 122%; clip: rect(3.159em 1000.5em 4.15em -1000em); top: -3.996em; font-family: MathJax_Math; font-style: italic;">I</span><span style="position: absolute; width: 0.869em; height: 0px; font-size: 70.7%; clip: rect(1.469em 1002.2em 2.653em -1000em); top: -3.846em; font-family: MathJax_Main;">2</span> , a reasonable choice for comparing them might be the <span style="font-weight: bold;">L1 distance</span>:</div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [1].png" type="image/png" data-filename="Image.png"/></div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [1].jpg" type="image/jpeg" data-filename="Image.jpg"/></div><div><br/></div><div>        An example of using pixel-wise differences to compare two images with L1 distance (for one color channel in this example). Two images are subtracted elementwise and then all differences are added up to a single number. If two images are identical the result will be zero. But if the images are very different the result will be large.</div><div><br/></div><div>        If you ran this code, you would see that this classifier only achieves <span style="font-weight: bold;">38.6%</span> on CIFAR-10.</div><div>        <span style="font-weight: bold;">The choice of distance.</span> There are many other ways of computing distances between vectors. Another common choice could be to instead use the <span style="font-weight: bold;">L2 distance</span>, which has the geometric interpretation of computing the euclidean distance between two vectors. The distance takes the form:</div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [2].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><br/></div><h3 style="text-align: center;"><span style="font-size: 24pt; color: rgb(28, 51, 135);">k - Nearest Neighbor Classifier</span></h3><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [2].jpg" type="image/jpeg" data-filename="Image.jpg"/></div><div><br/></div><div><br/></div><h3 style="text-align: left;"><span style="font-size: 18pt; color: rgb(28, 51, 135);">Validation sets for Hyperparameter tuning</span></h3><div>The k-nearest neighbor classifier requires a setting for <span style="font-style: italic;">k</span>. But what number works best? Additionally, we saw that there are <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">many different distance functions</span></font> we could have used: L1 norm, L2 norm, there are many other choices we didn’t even consider (e.g. dot products)<font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">. These choices are called hyperparameters</span></font> and they come up very often in the design of many Machine Learning algorithms that learn from data. It’s often not obvious what values/settings one should choose.</div><div><br/></div><div>        should think of the <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">test set as a very precious resource</span></font> that should ideally never be touched until one time at the very end.</div><div><ul><li>Evaluate on the test set only a single time, at the very end.</li></ul></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">validation set</span></div><div>        correct way of tuning the hyperparameters and it does not touch the test set at all.The idea is <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">to split our training set in two</span></font>: <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">a slightly smaller training set</span></font>, <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(167, 69, 0); font-weight: bold;">and</span></font> what we call a <span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">validation set</span>.</div><div>        Using CIFAR-10 as an example, we could for example use 49,000 of the training images for training, and leave 1,000 aside for validation. This validation set is essentially used as a fake test set to tune the hyper-parameters.</div><div><br/></div><div><font color="#328712" style="font-size: 24pt;"><span style="font-size: 24pt; color: rgb(50, 135, 18); font-weight: bold;">理解：</span></font></div><div><font color="#328712" style="font-size: 24pt;"><span style="font-size: 24pt; color: rgb(50, 135, 18); font-weight: bold;">Split your training set into training set and a validation set. Use validation set to tune all hyperparameters. At the end run a single time on the test set and report performance.</span></font></div><div><br/></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Cross-validation</span></div><div>        In cases where the size of your training data (and therefore also the validation data) <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">might be small</span></font>。</div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [3].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div>        instead of arbitrarily picking the first 1000 datapoints to be the validation set and rest training set, you can get a better and less noisy estimate of how well a certain value of <span style="font-style: italic;">k</span> works by iterating over different validation sets and averaging the performance across these.</div><div>        For example, in 5-fold cross-validation, we would <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">split the training data into 5 equal folds</span></font>, use 4 of them for training, and 1 for validation. We would <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">then iterate over which fold is the validation fold</span></font>, evaluate the performance, and finally average the performance across the different folds.</div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">In practice</span></div><div><font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">cross-validation can be computationally expensive.</span></font></div><div>However, this depends on multiple factors: For example if the number of hyperparameters is large you may prefer to use bigger validation splits. If the number of examples in the validation set is small (perhaps only a few hundred or so), it is safer to use cross-validation. Typical number of folds you can see in practice would be 3-fold, 5-fold or 10-fold cross-validation.</div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Pros and Cons of Nearest Neighbor classifier</span></div><div>disadvantages:</div><ul><li>The classifier must <span style="font-style: italic;">remember</span> all of the training data and store it for future comparisons with the test data. This is space inefficient because datasets may easily be gigabytes in size.</li><li>Classifying a test image is expensive since it requires a comparison to all training images.</li></ul><h3><span style="font-size: 18pt; color: rgb(28, 51, 135);">Summary: Applying kNN in practice</span></h3><div style="margin-top: 1em; margin-bottom: 1em;">If you wish to apply kNN in practice (hopefully not on images, or perhaps as only a baseline) proceed as follows:</div><ol><li>Preprocess your data: Normalize the features in your data (e.g. one pixel in images) to have zero mean and unit variance. We will cover this in more detail in later sections, and chose not to cover data normalization in this section because pixels in images are usually homogeneous and do not exhibit widely different distributions, alleviating the need for data normalization.</li><li>If your data is very high-dimensional, consider using a dimensionality reduction technique such as PCA (<a href="http://en.wikipedia.org/wiki/Principal_component_analysis">wiki ref</a>, <a href="http://cs229.stanford.edu/notes/cs229-notes10.pdf">CS229ref</a>, <a href="http://www.bigdataexaminer.com/understanding-dimensionality-reduction-principal-component-analysis-and-singular-value-decomposition/">blog ref</a>) or even <a href="http://scikit-learn.org/stable/modules/random_projection.html">Random Projections</a>.</li><li>Split your training data randomly into train/val splits. As a rule of thumb, between 70-90% of your data usually goes to the train split. This setting depends on how many hyperparameters you have and how much of an influence you expect them to have. If there are many hyperparameters to estimate, you should err on the side of having larger validation set to estimate them effectively. If you are concerned about the size of your validation data, it is best to split the training data into folds and perform cross-validation. If you can afford the computational budget it is always safer to go with cross-validation (the more folds the better, but more expensive).</li><li>Train and evaluate the kNN classifier on the validation data (for all folds, if doing cross-validation) for many choices of <span style="font-weight: bold;">k</span> (e.g. the more the better) and across different distance types (L1 and L2 are good candidates)</li><li>If your kNN classifier is running too long, consider using an Approximate Nearest Neighbor library (e.g. <a href="http://www.cs.ubc.ca/research/flann/">FLANN</a>) to accelerate the retrieval (at cost of some accuracy).</li><li>Take note of the hyperparameters that gave the best results. There is a question of whether you should use the full training set with the best hyperparameters, since the optimal hyperparameters might change if you were to fold the validation data into your training set (since the size of the data would be larger). In practice it is cleaner to not use the validation data in the final classifier and consider it to be <span style="font-style: italic;">burned</span> on estimating the hyperparameters. Evaluate the best model on the test set. Report the test set accuracy and declare the result to be the performance of the kNN classifier on your data.</li></ol><div><br/></div><div><br/></div></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><h2 style="text-align: center;"><span style="font-size: 24pt; color: rgb(28, 51, 135);">Linear Classification</span></h2><div>        develop a more powerful approach to image classification that we will eventually naturally extend to entire Neural Networks and Convolutional Neural Networks.</div><div>        The approach will have two major components:</div><div><ul><li><span style="line-height: 1.45;">a</span> <span style="font-weight: bold; line-height: 1.45;">score function</span> <span style="line-height: 1.45;">that maps the raw data to class scores</span></li><li>a <span style="font-weight: bold;">loss function</span> that quantifies the agreement between the predicted scores and the ground truth labels.then cast this as <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">an optimization problem</span></font> in which we will <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">minimize the loss function</span></font> with respect to the parameters of the score function.</li></ul></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: normal;">Parameterized mapping from images to label scores</span></h3><div><font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">score function：</span></font></div><div><img src="Module 1 Neural Networks_files/Image [4].png" type="image/png" data-filename="Image.png"/></div><div><span style="font-weight: bold;">Linear classifier.</span>  start out with arguably the simplest possible function, a linear mapping:</div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [5].png" type="image/png" data-filename="Image.png"/></div><div><img src="Module 1 Neural Networks_files/Image [6].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: normal;">Interpreting a linear classifier</span></h3><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [3].jpg" type="image/jpeg" data-filename="Image.jpg" width="878"/></div><div><br/></div><div><br/></div><div>computes the score of a class as a weighted sum of all of its pixel values across <span style="font-size: 12pt; color: rgb(173, 0, 0);">all 3 of its color channels</span>.</div><div><font color="#AD0000" style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">the function has the capacity to like or dislike (depending on the sign of each weight) certain colors at certain positions in the image.</span></font></div><div><br/></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Analogy of images as high-dimensional points</span></div><div>        Since the images are stretched into high-dimensional column vectors, we can interpret each image as a single point in this space (e.g. <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">each image in CIFAR-10 is a point in 3072-dimensional space of 32x32x3 pixels</span></font>). Analogously, the entire dataset is a (labeled) set of points.</div><div><br/></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Interpretation of linear classifiers as template matching</span></div><div>instead of having thousands of training images we are only using a single image per class (although we will learn it, and it does not necessarily have to be one of the images in the training set), and we use the (negative) inner product as the distance instead of the L1 or L2 distance.</div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [7].png" type="image/png" data-filename="Image.png"/></div><div>        Additionally, note that the horse template seems to contain a two-headed horse, which is due to both left and right facing horses in the dataset. <span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">The linear classifier</span> <span style="font-size: 12pt; color: rgb(173, 0, 0); font-style: italic; font-weight: bold;">merges</span> <span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">these two modes of horses in the data into a single template.</span> Similarly, the car classifier seems to have merged several modes into a single template which has to identify cars from all sides, and of all colors. In particular, this template ended up being red, which hints that there are more red cars in the CIFAR-10 dataset than of any other color. The linear classifier is too weak to properly account for different-colored cars, but as we will see later neural networks will allow us to perform this task. Looking ahead a bit, a neural network will be able to <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">develop intermediate neurons in its hidden layers that could detect specific car types</span></font> (e.g. green car facing left, blue car facing front, etc.), and <span style="color: rgb(173, 0, 0); font-weight: bold;">neurons on the next layer could combine these into a more accurate car score</span> through a weighted sum of the individual car detectors.</div><div><br/></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Bias trick</span></div><div>a common simplifying trick to representing the two parameters<img src="Module 1 Neural Networks_files/Image [8].png" type="image/png" data-filename="Image.png"/> <span style="position: absolute; width: 1.947em; height: 0px; font-size: 122%; clip: rect(1.509em 1001.94em 2.704em -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">W</span><span style="position: absolute; width: 1.947em; height: 0px; font-size: 122%; clip: rect(1.509em 1001.94em 2.704em -1000em); top: -2.357em; font-family: MathJax_Main;">,</span><span style="position: absolute; width: 1.947em; height: 0px; font-size: 122%; clip: rect(1.509em 1001.94em 2.704em -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">b</span> as one.</div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [9].png" type="image/png" data-filename="Image.png" width="800"/></div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Image data preprocessing</span></div><div>        As a quick note, in the examples above we used the raw pixel values (which <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">range from [0…255]</span></font>). In Machine Learning, it is a very common practice to <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">always perform normalization of your input features</span></font> (in the case of images, every pixel is thought of as a feature). In particular, it is important to <span style="font-weight: bold;">center your data</span> by subtracting the mean from every feature. In the case of images, this corresponds to computing a <span style="font-style: italic;">mean image</span> across the training images and subtracting it from every image to get images where the pixels <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">range from approximately [-127 … 127]</span></font>. Further common preprocessing is to scale each input feature so that its values <font style="font-size: 12pt;"><span style="font-size: 12pt; color: rgb(173, 0, 0); font-weight: bold;">range from [-1, 1]</span></font>. Of these, zero mean centering is arguably more important but we will have to wait for its justification until we understand the dynamics of gradient descent.</div><div><br/></div><div><br/></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135);">Loss function</span></h3><div>We are going to measure our unhappiness with outcomes such as this one with a <span style="font-weight: bold;">loss function</span> (or sometimes also referred to as the <span style="font-weight: bold;">cost function</span> or the <span style="font-weight: bold;">objective</span>). Intuitively, the loss will be high if we’re doing a poor job of classifying the training data, and it will be low if we’re doing well.</div><div><br/></div><h4><span style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: normal;">Multiclass Support Vector Machine loss</span></h4><h4><span style="line-height: 1.45;">several ways to define the details of the loss function</span></h4><div><ul><li><span style="font-weight: bold;">Multiclass Support Vector Machine</span> (SVM) loss.</li></ul></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135);">Practical Considerations</span></h3><div><ul><li><span style="font-weight: bold;">Setting Delta.</span></li><li><span style="font-weight: bold;">Relation to Binary Support Vector Machine</span><span style="font-weight: bold;">.</span></li><li><span style="font-weight: bold;">Aside: Optimization in primal</span><span style="font-weight: bold;">.</span></li><li><span style="font-weight: bold;">Aside: Other Multiclass SVM formulations.</span></li></ul></div><div><br/></div><div><br/></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135);">Softmax classifier</span></h3><div><br/></div><div><br/></div><div><br/></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135);">SVM vs. Softmax</span></h3><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [10].png" type="image/png" data-filename="Image.png" width="842"/></div><div><br/></div><div><br/></div><div>Example of the difference between the SVM and Softmax classifiers for one datapoint. In both cases we compute the same score vector <span style="font-weight: bold;">f</span> (e.g. by matrix multiplication in this section). The difference is in the interpretation of the scores in <span style="font-weight: bold;">f</span>: The SVM interprets these as class scores and its loss function encourages the correct class (class 2, in blue) to have a score higher by a margin than the other class scores. The Softmax classifier instead interprets the scores as (unnormalized) log probabilities for each class and then encourages the (normalized) log probability of the correct class to be high (equivalently the negative of it to be low). The final loss for this example is 1.58 for the SVM and 1.04 (note this is 1.04 using the natural logarithm, not base 2 or base 10) for the Softmax classifier, but note that these numbers are not comparable; They are only meaningful in relation to loss computed within the same classifier and with the same data.</div><div><br/></div><div><span style="font-size: 18pt; color: rgb(28, 51, 135);">Softmax classifier provides “probabilities” for each class</span></div><div>Unlike the SVM which computes uncalibrated and not easy to interpret scores for all classes, the Softmax classifier allows us to compute “probabilities” for all labels.</div><div><br/></div><div><span style="font-weight: bold;">In practice, SVM and Softmax are usually comparable.</span> The performance difference between the SVM and Softmax are usually very small, and different people will have different opinions on which classifier works better. Compared to the Softmax classifier, the SVM is a more <span style="font-style: italic;">local</span> objective, which could be thought of either as a bug or a feature. Consider an example that achieves the scores [10, -2, 3] and where the first class is correct.</div><div><br/></div><div><br/></div><h3><span style="font-size: 18pt; color: rgb(28, 51, 135);">Summary</span></h3><div style="margin-top: 1em; margin-bottom: 1em;">In summary,</div><ul><li>We defined a <span style="font-weight: bold;">score function</span> from image pixels to class scores (in this section, a linear function that depends on weights <span style="font-weight: bold;">W</span> and biases <span style="font-weight: bold;">b</span>).</li><li>Unlike kNN classifier, the advantage of this <span style="font-weight: bold;">parametric approach</span> is that once we learn the parameters we can discard the training data. Additionally, the prediction for a new test image is fast since it requires a single matrix multiplication with <span style="font-weight: bold;">W</span>, not an exhaustive comparison to every single training example.</li><li>We introduced the <span style="font-weight: bold;">bias trick</span>, which allows us to fold the bias vector into the weight matrix for convenience of only having to keep track of one parameter matrix.</li><li>We defined a <span style="font-weight: bold;">loss function</span> (we introduced two commonly used losses for linear classifiers: the <span style="font-weight: bold;">SVM</span> and the <span style="font-weight: bold;">Softmax</span>) that measures how compatible a given set of parameters is with respect to the ground truth labels in the training dataset. We also saw that the loss function was defined in such way that making good predictions on the training data is equivalent to having a small loss.</li></ul><div>We now saw one way to take a dataset of images and map each one to class scores based on a set of parameters, and we saw two examples of loss functions that we can use to measure the quality of the predictions. But how do we efficiently determine the parameters that give the best (lowest) loss? This process is <span style="font-style: italic;">optimization</span>, and it is the topic of the next section.</div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div style="text-align: center;"><div><br/></div></div><div style="text-align: center;"><a href="http://cs231n.github.io/optimization-1/" style="font-size: 24pt;"></a><a href="http://cs231n.github.io/optimization-1/" style="color: rgb(28, 51, 135); font-size: 24pt; font-weight: bold;">Optimization: Stochastic Gradient Descent</a></div><div style="text-align: left;"><div><img src="Module 1 Neural Networks_files/Image [11].png" type="image/png" data-filename="Image.png"/></div></div><div><font color="#1C3387" style="font-size: 18pt;"><br/></font></div><div><font color="#1C3387" style="font-size: 18pt;">Foreshadowing</font></div><div><br/></div><div><span>    <span>    </span></span>Once we understand how these three core components interact, we will revisit the first component (the parameterized function mapping) and extend it to functions much more complicated than a linear mapping: First entire Neural Networks, and then Convolutional Neural Networks. The loss functions and the optimization process will remain relatively unchanged.</div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><h3 style="text-align: center;"><font color="#1C3387" style="font-size: 24pt;">Visualizing the loss function</font></h3><div style="text-align: left;"><span style="line-height: 1.45;">    </span><span style="line-height: 1.45;">    The <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>loss functions</b></font> we’ll look at in this class are usually defined <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>over very high-dimensional spaces</b></font> (e.g. in CIFAR-10 a linear classifier weight matrix is of size [10 x 3073] for a total of 30,730 parameters), making them <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>difficult to visualize</b></font>.</span><br/></div><div><span>    <span>    However, we can still gain some intuitions about one by slicing through the high-dimensional space along rays (1 dimension), or along planes (2 dimensions).</span></span><br/></div><div><span><span>    <span>    For example：</span></span><br/></span></div><div><ul><li>generate a random weight matrix <img src="Module 1 Neural Networks_files/Image [12].png" type="image/png" data-filename="Image.png"/><span style="position: absolute; width: 1.025em; height: 0px; font-size: 122%; clip: rect(1.52em, 1001.03em, 2.532em, -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">W</span> (which corresponds to a single point in the space)</li><li>march along a ray and record the loss function value along the way.</li><li>can generate a random direction<img src="Module 1 Neural Networks_files/Image [13].png" type="image/png" data-filename="Image.png"/> <span style="position: absolute; width: 1.373em; height: 0px; font-size: 122%; clip: rect(3.159em, 1001.05em, 4.172em, -1000em); top: -3.996em; font-family: MathJax_Math; font-style: italic;">W</span><span style="position: absolute; width: 1.373em; height: 0px; font-size: 70.7%; clip: rect(1.417em, 1001.38em, 2.558em, -1000em); top: -3.846em; font-family: MathJax_Main;">1</span> and compute the loss along this direction by evaluating<img src="Module 1 Neural Networks_files/Image [14].png" type="image/png" data-filename="Image.png"/> <span style="position: absolute; width: 5.635em; height: 0px; font-size: 122%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">L</span><span style="position: absolute; width: 5.635em; height: 0px; font-size: 122%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -2.357em; font-family: MathJax_Main;">(</span><span style="position: absolute; width: 5.635em; height: 0px; font-size: 122%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">W</span><span style="position: absolute; width: 5.635em; height: 0px; font-size: 122%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -2.357em; font-family: MathJax_Main;">+</span><span style="position: absolute; width: 5.635em; height: 0px; font-size: 122%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">a</span><span style="position: absolute; width: 1.373em; height: 0px; font-size: 122%; clip: rect(3.159em, 1001.05em, 4.172em, -1000em); top: -3.996em; font-family: MathJax_Math; font-style: italic;">W</span><span style="position: absolute; width: 1.373em; height: 0px; font-size: 70.7%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -3.846em; font-family: MathJax_Main;">1</span><span style="position: absolute; width: 5.635em; height: 0px; font-size: 122%; clip: rect(1.453em, 1005.54em, 2.76em, -1000em); top: -2.357em; font-family: MathJax_Main;">)</span> for different values of <span style="position: absolute; width: 0.512em; height: 0px; font-size: 122%; clip: rect(1.762em, 1000.49em, 2.52em, -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">a</span><img src="Module 1 Neural Networks_files/Image [15].png" type="image/png" data-filename="Image.png"/></li><li>generates a simple plot with the value of <span style="position: absolute; width: 0.512em; height: 0px; font-size: 122%; clip: rect(1.762em, 1000.49em, 2.52em, -1000em); top: -2.357em; font-family: MathJax_Math; font-style: italic;">a</span> as the x-axis and the value of <img src="Module 1 Neural Networks_files/Image [16].png" type="image/png" data-filename="Image.png"/>the loss function as the y-axis.</li></ul></div><div><br/></div><div><img src="Module 1 Neural Networks_files/Image [17].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><br/></div><h3><font color="#1C3387" style="font-size: 18pt;">Optimization</font></h3><h4><font color="#1C3387" style="font-size: 18pt; font-weight: normal;">Strategy #1: A first very bad idea solution: Random search</font></h4><div><ul><li><span style="font-weight: bold; line-height: 1.45;">Core idea: iterative refinement : o</span><span style="font-weight: bold; line-height: 1.45;">ur approach will be to start with a random</span> <span style="font-weight: bold; line-height: 1.45;">W</span> <span style="font-weight: bold; line-height: 1.45;">and then iteratively refine it, making it slightly better each time.</span><br/></li><li><span style="font-weight: bold;">Blindfolded hiker analogy</span></li></ul></div><div><br/></div><h4><font color="#1C3387" style="font-size: 18pt; font-weight: normal;">Strategy #2: Random Local Search</font></h4><div><img src="Module 1 Neural Networks_files/Image [18].png" type="image/png" data-filename="Image.png"/></div><h4><font color="#1C3387" style="font-size: 18pt; font-weight: normal;">Strategy #3: Following the Gradient</font></h4><div><span style="line-height: 1.45;"><span>    <span>    </span></span>no need to randomly search for a good direction : This direction will be related to the <span style="font-weight: bold;">gradient</span> of the loss function. In our hiking analogy, this approach roughly corresponds to feeling the slope of the hill below our feet and stepping down the direction that feels steepest.</span><br/></div><div><span>    <span>    we call the derivatives <span style="font-weight: bold;">partial derivatives</span>, and the gradient is simply the vector of partial derivatives in each dimension.</span></span><br/></div><div style="text-align: center;"><img src="Module 1 Neural Networks_files/Image [19].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><h3><font style="font-size: 18pt; color: rgb(28, 51, 135);">Computing the gradient</font></h3><div>two ways to compute the gradient：</div><div><ul><li>A slow, approximate but easy way (<span style="font-weight: bold;">numerical gradient</span>)</li><li>a fast, exact but more error-prone way that requires calculus (<span style="font-weight: bold;">analytic gradient</span>)</li></ul></div><h4><font style="font-size: 18pt; color: rgb(28, 51, 135); font-weight: normal;">Computing the gradient numerically with finite differences</font></h4><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">def eval_numerical_gradient(f, x):</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>  <span>    <span>    </span></span></span> &quot;&quot;&quot;</span></div></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">a naive implementation of numerical gradient of f at x</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">- f should be a function that takes a single argument</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">- x is the point (numpy array) to evaluate the gradient at</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">&quot;&quot;&quot;</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">fx = f(x) # evaluate function value at original point</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">grad = np.zeros(x.shape)</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">h = 0.00001</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"># iterate over all indexes in x</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">while not it.finished:</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"># evaluate function at x+h</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">ix = it.multi_index</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">old_value = x[ix]</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">x[ix] = old_value + h # increment by h</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">fxh = f(x) # evalute f(x + h)</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">x[ix] = old_value # restore to previous value (very important!)</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"># compute the partial derivative</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">grad[ix] = (fxh - fx) / h # the slope</span></div></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">it.iternext() # step to next dimension</span></div></blockquote></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">return grad</span></div><div><br/></div></blockquote><div><span>    <span>    </span></span>Following the gradient formula we gave above, the code above <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>iterates over all dimensions one by one</b></font>, makes <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>a small change h</b></font> along that dimension and calculates the partial derivative of the loss function along that dimension by seeing how much the function changed. The variable grad holds the full gradient in the end.</div><div><ul><li><span style="font-weight: bold;">Practical considerations</span>.better to compute the numeric gradient using the <span style="font-weight: bold;">centered difference formula：<img src="Module 1 Neural Networks_files/Image [20].png" type="image/png" data-filename="Image.png" style="font-weight: bold;"/></span></li><li><span style="font-weight: bold;">Update in negative gradient direction</span><span style="font-weight: bold;">.</span></li><li><span style="font-weight: bold;">Effect of step size： </span><span style="font-weight: bold;"><span style="font-weight: bold;">called the</span> <span style="font-style: italic; font-weight: bold;">learning rate</span></span></li><li><span style="font-weight: bold; font-style: italic;">A problem of efficiency</span><span style="font-weight: bold; font-style: italic;">.</span></li></ul></div><div><br/></div><div><br/></div><div><img src="Module 1 Neural Networks_files/Image [21].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><h3><font style="font-size: 18pt; color: rgb(28, 51, 135);">Gradient Descent</font></h3><div><span style="line-height: 1.45;">simple loop is at the core of all Neural Network libraries</span><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"># Vanilla Gradient Descent</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">while True:</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    </span>weights_grad = evaluate_gradient(loss_fun, data, weights)</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    </span>weights += - step_size * weights_grad # perform parameter update</span></div></div><div><br/></div><div><ul><li><span style="font-weight: bold;">Mini-batch gradient descent.</span></li></ul><div><span>    <span>    <span>    </span></span></span>wasteful to compute the full loss function over the entire training set in order to perform only a single parameter update.</div></div><div><span>    <span>        to compute the gradient over <span style="font-weight: bold;">batches</span> of the training data。<font color="#AD0000" style="font-size: 12pt;"><b>For example, in current state of the art ConvNets, a typical batch contains 256 examples from the entire <span> </span></b></font></span></span><b style="font-size: 12pt; color: rgb(173, 0, 0); line-height: 1.45;">  training set of 1.2 million. This batch is then used to perform a parameter update:</b></div><div><img src="Module 1 Neural Networks_files/Image [22].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><br/></div><h3><font color="#1C3387" style="font-size: 18pt;">Summary</font></h3><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div style="text-align: center;"><font color="#1C3387" style="font-size: 24pt;"><b><br/></b></font></div><div style="text-align: center;"><a href="http://cs231n.github.io/optimization-2/"><font color="#1C3387" style="font-size: 24pt;"><b>Backpropagation, Intuitions</b></font></a></div><div style="text-align: center;"><br/></div><div><img src="Module 1 Neural Networks_files/Image [23].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><img src="Module 1 Neural Networks_files/Image [24].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><img src="Module 1 Neural Networks_files/Image [25].png" type="image/png" data-filename="Image.png"/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><img src="Module 1 Neural Networks_files/Image [26].png" type="image/png" data-filename="Image.png" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div></div><div><br/></div><div>At the end we are left with the gradient in the variables [dfdx,dfdy,dfdz], which tell us the sensitivity of the variables x,y,z on f!. This is the simplest example of backpropagation.</div><div><font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>visualized：</b></font></div><div><img src="Module 1 Neural Networks_files/Image [27].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><br/></div><div><br/></div><h3>Summary</h3><ul><li>We developed intuition for what the gradients mean, how they flow backwards in the circuit, and how they communicate which part of the circuit should increase or decrease and with what force to make the final output higher.</li><li>We discussed the importance of <span style="font-weight: bold;">staged computation</span> for practical implementations of backpropagation. You always want to break up your function into modules for which you can easily derive local gradients, and then chain them with chain rule. Crucially, you almost never want to write out these expressions on paper and differentiate them symbolically in full, because you never need an explicit mathematical equation for the gradient of the input variables. Hence, decompose your expressions into stages such that you can differentiate every stage independently (the stages will be matrix vector multiplies, or max operations, or sum operations, etc.) and then backprop through the variables one step at a time.</li></ul><div><span style="-en-paragraph: true;">In the next section we will start to define Neural Networks, and backpropagation will allow us to efficiently compute the gradients on the connections of the neural network, with respect to a loss function. In other words, we’re now ready to train Neural Nets, and the most conceptually difficult part of this class is behind us! ConvNets will then be a small step away.</span></div><div><br/></div><div><br/></div><div><br/></div></div></span>
</div></body></html> 